package BackTracking.segmentation;

import java.util.ArrayList;
import java.util.List;

class Solution {

    static List<String> res = new ArrayList<>();
    public static  List<String> restoreIpAddresses(String s) {
        if(s==null || s.length()<1){
            return res;
        }

        backTrack(s, 0);
        return res;
    }


    static List<String> path = new ArrayList<>(); //记录路程

    private static void backTrack(String s, int startIndex){


        //找到一组，拼接结果
        if(startIndex >= s.length() && path.size() == 4){
            String str = "";
            for(int i=0;i<path.size();i++){
                if(i!=path.size()-1){
                    str += path.get(i) + ".";
                }else{
                    str += path.get(i);
                }

            }
            res.add(str);
            return;
        }

        for(int i=startIndex;i<s.length();i++){
            if(isValid(s,startIndex,i)){
                path.add(s.substring(startIndex,i+1));
                backTrack(s,i+1);
                path.remove(path.size()-1);
            }
        }
    }



    // 判断字符串s在左闭⼜闭区间[start, end]所组成的数字是否合法
    private static boolean isValid(String s, int startIndex, int end){
        //越界
        if(startIndex>end){
            return false;
        }

        //开头不能是0
        if(s.charAt(startIndex)=='0'){
            return false;
        }

        int num = 0;
        //其中不能有非数字符号
        for(int i=startIndex;i<=end;i++){
            if(s.charAt(i)-'0' > 9 || s.charAt(i)-'0' < 0 ){
                return false;
            }
            //数字在0-255之间
            num = num * 10 + (s.charAt(i) - '0');
            if(num<0 || num>255){
                return false;
            }
        }


        return true;
    }

    public static void main(String[] args) {
        System.out.println(restoreIpAddresses("25525511135"));
    }
}
